# 模拟退火法
import random
import math


N=50


def num_of_conflict(status):  # 获取该状态下互相攻击的皇后对数
    num_of_conflict = 0
    for col1 in range(0, N-1):
        for col2 in range(col1 + 1, N):
            if (status[col1] == status[col2]) \
                    or ((col2 - col1) == abs(status[col1] - status[col2])):  # 判断是否相互攻击
                num_of_conflict += 1
    return num_of_conflict


def solve(status, T):  # 根据递减的T和当前状态返回一个新状态
    next_status = []

    for col in range(0, N):
        for row in range(0, N):
            new_status = status[:]
            if status[col] != row:
                new_status[col] = row
                next_status.append(new_status)
    choose_status = random.randint(0, N*(N-1)-1)  # 从56个邻居任选一个
    if num_of_conflict(next_status[choose_status]) <= num_of_conflict(status):  # 新的状态优于原先的
        return next_status[choose_status]
    else:  # 原先的状态优于新状态
        E = num_of_conflict(status) - num_of_conflict(next_status[choose_status])
        probability = math.e ** (E / T)  # 概率计算公式
        choose = random.randint(0, 1000) / 1000
        if choose <= probability:  # 以一定概率使新的状态取代原先的状态
            return next_status[choose_status]
    return status  # 返回原状态，不移动


def init_status():
    status = []
    for i in range(N):  # 0~N-1
        status.append(random.randint(0, N-1))
    return status


status = init_status()
# for col in range(N):
#     row = random.randint(0, N-1)
#     status[col] = row
print("the initial status: ")
print(status)
print("the num of conflict: ")
print(num_of_conflict(status))
T = 5.0  # 初始T，（温度）
while num_of_conflict(status) > 0:  # 找不到最优解
    new_status = solve(status, T)  # 获取新状态
    if new_status == status:  # 不移动
        print("E < 0, but no move")
    else:
        status = new_status
        print("the new status: ")
        print(status)
        print("the num of conflict: ")
        print(num_of_conflict(status))
        if num_of_conflict(status) == 0:
            print("find a answer!")
    T = T * 0.99  # T递减，概率也递减
    if T < 0.0001:  # 运行 1077 次，此时认为T接近0
        print("T = 0, can't find a answer")
        break
